`
https://leetcode.cn/problems/matchsticks-to-square/
`

/**
 * @param {number[]} matchsticks
 * @return {boolean}
 */
var makesquare = function (matchsticks) {
  // 该题本质：是否可以把数组 matchsticks 分成 4 个和相等的子集
  return canPartitionKSubsets(matchsticks, 4)
};

// https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
var canPartitionKSubsets = function (nums, k) {
  const sum = nums.reduce((pre, cur) => pre + cur, 0);
  if (sum % k != 0) return false;
  const target = sum / k;
  nums.sort((a, b) => b - a);
  const buckets = new Array(k).fill(0);
  const backtrack = (index) => {
    if (index == nums.length) {
      return true;
    }
    for (let i = 0; i < k; i++) {
      if (i > 0 && buckets[i] == buckets[i - 1]) continue;
      if (buckets[i] + nums[index] > target) continue;
      buckets[i] += nums[index];
      if (backtrack(index + 1)) return true;
      buckets[i] -= nums[index];
    }
    return false;
  };
  return backtrack(0);
};